package lc_1782_统计点对的数目;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {

	private int hash(int u, int v) {
		if (u > v) {
			return (v << 15) | u;
		}
		return (u << 15) | v;
	}

	public int[] countPairs(int n, int[][] edges, int[] queries) {
		int[] cnts = new int[n + 1];
		arr = new int[100005];
		Map<Integer, Integer> uv = new HashMap<>();
		for (int[] e : edges) {
			int u = e[0], v = e[1];
			cnts[u]++;
			cnts[v]++;
			int h = hash(u, v);
			uv.put(h, uv.getOrDefault(h, 0) + 1);
		}
		int[] ans = new int[queries.length];
		for (int i = 1; i <= n; i++) {
			int s1 = cnts[i];
			for (int j = 0; j < queries.length; j++) {
				int q = queries[j];
				if (s1 > q) {
					ans[j] += i - 1; // 本身够大，(i前面,i)都满足
				} else {
					ans[j] += i - 1 - query(q - s1);
				}
			}
			add(s1);
		}
		Set<Integer> set = new HashSet<>();
		for (int[] e : edges) {
			int u = e[0], v = e[1];
			int h = hash(u, v);
			if (set.contains(h)) {
				continue;
			}
			set.add(h);
			int s = cnts[u] + cnts[v];
			int b = uv.get(h);
			for (int j = 0; j < queries.length; j++) {
				int q = queries[j];
				if (s > q && s - b <= q) {
					ans[j]--;
				}
			}
		}
		return ans;
	}

	int[] arr;

	private int lowbit(int x) {
		return x & -x;
	}

	private void add(int s) {
		s += 1;
		while (s < 100005) {
			arr[s]++;
			s += this.lowbit(s);
		}
	}

	private int query(int s) {
		s += 1;
		int ans = 0;
		while (s > 0) {
			ans +=arr[s];
			s -= this.lowbit(s);
		}
		return ans;
	}

	public static void main(String[] args) {
		System.out.println(Arrays.binarySearch(new int[] { 1, 3, 5, 7, 9 }, 0));
		System.out.println(Arrays.binarySearch(new int[] { 1, 3, 5, 7, 9 }, 1));
		System.out.println(Arrays.binarySearch(new int[] { 1, 3, 5, 7, 9 }, 4));
		System.out.println(Arrays.binarySearch(new int[] { 1, 3, 5, 7, 9 }, 5));
		System.out.println(Arrays.binarySearch(new int[] { 1, 3, 5, 7, 9 }, 6));
		System.out.println(Arrays.binarySearch(new int[] { 1, 3, 5, 7, 9 }, 9));
		System.out.println(Arrays.binarySearch(new int[] { 1, 3, 5, 7, 9 }, 10));
		int i = 0;
		while ((1 << i) <= 20000) {
			i++;
		}
		System.out.println(i);
		Solution so = new Solution();
		int[] ans = so.countPairs(5, new int[][] {{4,5},{1,3},{1,4}}, new int[] {1});
		System.out.println(ans[0]);
		//		5
//		[[4,5],[1,3],[1,4]]
//		[0,1,0,0,1,1,0,0,0,0,1,0,0,1,0,1,1,2]
		
// 		[10,8,10,10,8,8,10,10,10,10,8,10,10,8,10,8,8,3]
//      [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,4]
	}
}
